// https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table/
// 几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第k小的数字吗？
// 给定高度m 、宽度n 的一张 m * n的乘法表，以及正整数k，你需要返回表中第k 小的数字。
/*
乘法表:
1	2	3
2	4	6
3	6	9

第5小的数字是 3 (1, 2, 2, 3, 3).


1	2	3   4   5   6
2	4	6   8   10  12
3   6   9   12  15  18
4   8   12  16  20  24
5   10  15  20  25  30



第6小的数字是 6 (1, 2, 2, 3, 4, 6).



*/
#include <vector>
#include <iostream>

using namespace std;


class Solution {
public:
    int findKthNumber(int m, int n, int k) {
		int left = 1;
		int right = m * n;
		
		while(left < right){
			int mid = (left + right) / 2;
			int num = getNum(m, n, mid);
			cout << "num:" << num << endl;
			if(num >= k){
				right = mid;
			}else{
				left = mid + 1;
			}
		}
		return left;
    }
	
	int getNum(int m, int n, int num){
		int count = 0;
		for(int i = 1; i <= m; i++){
			count += min(num/i, n);
		}
		return count;
	}
};

int main(){
	Solution so;
	int num = so.findKthNumber(2, 3, 6);
	cout << num << endl;
	return 0;
}

